package com.lsa.letcode.the43.multStr;

public class Solution {
    public String multiply(String num1, String num2) {
    	if (num1.length() < num2.length()) {
    		String t = num1;
    		num1 = num2;
    		num2 = t;
    	}
    	
    	CharSequence result = new StringBuilder("0");
    	
    	for (int i = num2.length() - 1; i > -1 ; --i) {
    		int n2 = num(num2.charAt(i));
    		StringBuilder tmpResult = multiply(num1, n2);
    		tmpResult = multiply10(tmpResult, num2.length() - 1 - i);
    		result = add(result, tmpResult);
    	}
        return result.toString();
    }
    
	StringBuilder multiply(String num, int n) {
		StringBuilder r = new StringBuilder(num.length() + 1);
		int carry = 0;
		for (int i = num.length() - 1; i > -1; --i) {
			int n1 = num(num.charAt(i));
			int d = n1 * n + carry;
			carry = d / 10;
			r.append(chr(d % 10));
		}
		if (carry != 0) {
			r.append(chr(carry));
		}
		return r.reverse();
	}
	
	StringBuilder multiply10(StringBuilder tmpResult, int cnt) {
		for (int j = 0; j < cnt; j++) {
			tmpResult.append('0');
		}
		return tmpResult;
	}

	CharSequence add(CharSequence num1, CharSequence num2) {
    	if (num1.length() < num2.length()) {
    		CharSequence t = num1;
    		num1 = num2;
    		num2 = t;
    	}
    	
		StringBuilder sum = new StringBuilder(num1.length() + 1);
		
		int lenDiff = num1.length() - num2.length();
		int carry = 0;
		boolean isZero = true;
		for (int i = num1.length() - 1; i > -1 ; --i) {
			int n1 = num(num1.charAt(i));
			int j = i - lenDiff;
			int n2 = 0;
			if (j > - 1) {
				n2 = num(num2.charAt(j));
			}
			int t = n1 + n2 + carry;
			int d = t % 10;
			isZero = isZero && d == 0;   
			sum.append(chr(d));
			carry = t / 10;
		}
		
		if (carry != 0) {
			isZero = false;
			sum.append(chr(carry));
		}
		if (!isZero) {
			return sum.reverse();
		}
		else {
			return new StringBuilder("0");
		}
    }
    
    int num(char c) {
    	return c - '0';
    }
    
    char chr(int n) {
    	return (char)('0' + n);
    }
}